package com.msb.datastructure;

/**
 * 归并排序测试
 *
 * @author dataexa
 * @Date 2023/11/20
 */
public class MergeSortTest {
    //    public static int[] arr = new int[]{1, 2, 5, 11, 4, 55, 12, 10, 0, -1};
    public static int[] arr = new int[]{1, 2, 5, 1, 6, 3};

    public static void main(String[] args) {
//        System.out.println(process(arr, 0, arr.length - 1));
//        process01(arr, 0, arr.length - 1);
//        CommonUtils.printArray(arr);
//        System.out.println(process2(arr, 0, arr.length - 1));
        process(arr, 0, arr.length - 1);
//        System.out.println();
    }

    // 1. 归并排序实现
    public static void process01(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int m = l + ((r - l) >> 1);
        process01(arr, l, m);
        process01(arr, m + 1, r);
        mergeSort01(arr, l, m, r);
    }

    public static void mergeSort01(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int temp = 0;
        int p1 = l;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {
            help[temp++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[temp++] = arr[p1++];
        }
        while (p2 <= r) {
            help[temp++] = arr[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }
    }

    // 归并拓展: 1、计算一个arr[L...R]范围的最大值
    public static int process(int[] arr, int L, int R) {
        if (L == R) {
            return arr[L];
        }
        int mid = L + ((R - L) >> 1); // 比(L+R)/2更快
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }

    //归并拓展: 2、arr[L...R]既要排好序，也要求小和
    public static int process2(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return process2(arr, l, mid) + process2(arr, mid + 1, r) + merge2(arr, l, mid, r);
    }

    private static int merge2(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = M + 1;
        int res = 0;
        while (p1 <= M && p2 <= R) {
            res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        for (int j = 0; j < help.length; j++) {
            arr[L + j] = help[j];
        }
        return res;
    }

    private static void mergeSort2(int[] arr, int l, int r) {
        if (l == r) {
            return;
        }
        int m = l + ((r - l) >> 1);
        mergeSort2(arr, l, m);
        mergeSort2(arr, m + 1, r);
        mergetest(arr, l, m, r);
    }

    private static void mergetest(int[] arr, int l, int m, int r) {
        int[] help = new int[r - l + 1];
        int temp = 0;
        int p1 = l;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {
            help[temp++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[temp++] = arr[p1++];
        }
        while (p2 <= r) {
            help[temp++] = arr[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i];
        }

    }

    //归并拓展: 3、arr[L...R]逆序对问题-左边的数如果比右边的数大，则这两个数构成一个逆序对

}